package binTree;

public class MyBinTree {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
        public static TreeNode build(){
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(6);
            TreeNode node7 = new TreeNode(7);
            node1.left = node2;
            node1.right = node4;
            node2.left = node3;
            node4.left = node5;
            node4.right = node6;
            node6.right = node7;
            boolean a=false;
            return node1;

        }
        //前序遍历
        //传入一个以root为根节点的二叉树,就能按照前序遍历的方式进行遍历,输出每个节点
        public static void preOrder(TreeNode root){
            if(root==null){
                return;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

        //中序遍历
        public static void inOrder(TreeNode root){
            if(root==null){
                return;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }

        public static void postOrder(TreeNode root){
            if (root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }

        public static int getNotes(TreeNode root){
            if(root==null){
                return 0;
            }
            return 1+getNotes(root.left)+getNotes(root.right);
        }

        public static int height(TreeNode root){
            if (root==null){
                return 0;
            }
            return 1+Math.max(height(root.left),height(root.right));
        }

        public static int getLeafNotes(TreeNode root){
            if(root==null){
                return 0;
            }
            if(root.left==null&&root.right==null){
                return 1;
            }
            return getLeafNotes(root.left)+getLeafNotes(root.right);
        }

        public static int getKLevelNotes(TreeNode root,int k){
            if(root==null||k==0){
                return 0;
            }
            if(k==1){
                return 1;
            }
            return getKLevelNotes(root.right,k-1)+getKLevelNotes(root.left,k-1);
        }

        public static boolean contains(TreeNode root,int val){
            if(root==null){
                return false;
            }
            if(root.val==val){
                return true;
            }
            return contains(root.left,val)||contains(root.right,val);
        }

        public static void main(String[] args) {
            TreeNode root = build();
            preOrder(root);
            System.out.println();
            inOrder(root);
            System.out.println();
            postOrder(root);
            System.out.println();
            System.out.println(getNotes(root));
            System.out.println(getLeafNotes(root));
            System.out.println(height(root));
            System.out.println(getKLevelNotes(root,3));
            System.out.println(contains(root,0));
        }

    }
}
